#include <stdio.h>
/*
 * 快速排序:
 * 每次选取一个中间元素pivot，      =========》一般选取第一个或者最后一个
 * 然后将小于Pivot 的值放到Pivot的左边    划分   得到左右两个无序集合
 * 大于pivot的值放到pivot的右边
 * 最后，对得到的左右子集进行同样的操作。  ==》递归
 * */
/*
 * 划分：
 * 1. 设置pivot
 * 2.设置两个左右指针，分别指向待排序范围的最左边和最右边
 * 3.如果Pivot取得是最左端的值，那左右指针移动一定要先移动右指针
 *    如果右指针指向的元素合格（arr[right] >mid）
 *        右指针就可以向前移动
 *      如果右指针指向的元素不合格
 *        右指针指向的元素放到空位子(left指向的位置)
 *
 *    如果左指针指向的元素合格
 *        左指针向后移动
 *     如果左指针指向的元素不合格
 *         左指针指向的元素放到右边的空位置（right的位置）
 * */
/*
 * 函数名：quick
 * 输入：无序的数组，左右位置
 * 输出：无
 * */
int partition(int arr[],int left,int right){
    //1.设置中间元素pivot
    int pivot =arr[left];
    //2.划分操作
    while(left<right){
        //2.1 先移动右指针
        while (left<right&& arr[right]>=pivot)
            right--;
        arr[left]=arr[right];
        //2.2 再移动左指针
        while(left<right && arr[left]<=pivot)
            left++;
        arr[right]=arr[left];
    }
    arr[left]=pivot;//将pivot放到正确的位置上
    return left;
}

void quickSort(int *arr,int left,int right){
    if(left<right){
        //1.划分
        int pivotPos = partition(arr,left,right);
        //2.递归调用处理左右子集
        quickSort(arr,left,pivotPos-1);
        quickSort(arr,pivotPos+1,right);
    }
}

int main() {
    int arr[5]={34,13,34,232,63};
    quickSort(arr,0,4);
   // printf("Hello, World!\n");
    return 0;
}
